//SD_class_New.cpp---------------生成新数独
//
//	bool SD_C::new_SD();        //通过随机算法填数独的1\3\5\7\9宫
//  void SD_C::SolveNewSD();    //生成数独终盘
//  void SD_C::NewUnknowSD();   //挖空生成新数独
//  bool SD_C::FindAnswer();    //递归判断多解
//
//v.1.0------------------------------------------------------------------

#include <iostream>
#include <random>

#include "SD_class.h"
#include "SD_ver.h"

using namespace std;

//1.通过随机算法填数独的1\3\5\7\9宫
//  返回一个bool值判断填空是否出错
bool SD_C::NewSD()
{
    random_device rd;                   //真随机数生成器，用于生成随机种子
    default_random_engine e(rd());      //随机数引擎
    uniform_int_distribution<> u(0, 8); //随机数范围

    for (int n = 0; n < 3; n++) //对对角线三个宫进行填空(1\5\9）
    {
        int t[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; //用来打乱的1~9数列

        for (int i = 3 * n; i < 3 + 3 * n; i++)
        {
            for (int j = 3 * n; j < 3 + 3 * n; j++)
            {
                do //通过随机生成数组底标来打乱数组
                {
                    int k = u(e);
                    q[i][j] = t[k]; //给q赋值
                    t[k] = 0;
                } while (q[i][j] == 0);
            }
        }
    }
    SimpleInit_s(); //刷新s数组
    AllFind();

    int qq;                     //准备填入的新数字
    short ss, s0;               //ss是通过qq得到的二进制数，s0用于判断ss是否在s[i][j]范围内
    for (int i = 0; i < 3; i++) //填第3宫
    {
        for (int j = 6; j < 9; j++)
        {
            do
            {
                qq = u(e) + 1;
                ss = 1 << (qq - 1);
                s0 = s[i][j] | ss; //判断ss是否在s[i][j]范围内，是则s0与s[i][j]相同，反之不同
            } while (s[i][j] != s0);
            q[i][j] = qq;
            s[i][j] = ss;
            SimpleInit_s();
            AllFind();
        }
    }
    if (Check_s() == -1)
        return false; //生成出错

    for (int i = 0; i < 3; i++) //填第7宫
    {
        for (int j = 6; j < 9; j++)
        {
            do
            {
                qq = u(e) + 1;
                ss = 1 << (qq - 1);
                s0 = s[j][i] | ss;
            } while (s[j][i] != s0);
            q[j][i] = qq;
            s[j][i] = ss;
            SimpleInit_s();
            AllFind();
        }
    }
    if (Check_s() == -1)
        return false; //生成出错

    return true; //生成成功（此时可能还有个别空未填）
}

//2.生成新的数独终盘
void SD_C::SolveNewSD()
{
    t = 0;
    int x[9][9] = {0};
    do //如果填1/3/5/7/9出错则重置q[]
    {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                q[i][j] = x[i][j];
    } while (NewSD() == false);
    cout << "新的数独终盘：" << endl;
    SolveOne(); //解出第一个解作为终盘
    Print_q(0);
}

//3.挖空，生成新的数独题目
void SD_C::NewUnknowSD()
{
    int old;
    int block[9] = {0};                 //存储每宫的空数
    int blocksum = 0;
    random_device rd;                   //真随机数生成器，作为引擎e的种子
    default_random_engine e(rd());      //随机数引擎，作为下列引擎的种子
    uniform_int_distribution<> u(0, 8); //生成范围0~8的随机数引擎
    uniform_int_distribution<> v(0, 2); //生成范围0~2的随机数引擎

    int k = u(e);
    for (int i = 0; i < 3; i++) //挖去k宫
        for (int j = 0; j < 3; j++)
        {
            x = k % 3 * 3 + i;
            y = k / 3 * 3 + j;
            q[x][y] = 0;
        }
    block[k] = 9;
    blocksum += block[k];

    for (int i = 0; i < 9; i++) //每宫挖1个
    {
        if (i != k)
        {
            x = v(e) + i % 3 * 3;
            y = v(e) + i / 3 * 3;
            q[x][y] = 0;
            block[i]++;
            blocksum++;
        }
        cout << i << "宫有" << block[i] << "空" << endl;
    }
    Print_q(1);

    // for (int i = 0; i < 30; i++)                    //每宫试挖i次
    // {
    //     for (int j = 0; j < 8; j++)                 //遍历9个宫
    //     {
    //         if (j != k)                             //排除已经挖空的宫
    //         {
    //             for (int a = 0; a < 3; a++)         //遍历宫内每个空
    //                 for (int b = 0; b < 3; b++)
    //                 {
    //                     x = a + j % 3 * 3;
    //                     y = b + j / 3 * 3;
    //                     if (q[x][y] != 0)
    //                     {
    //                         old = q[x][y];
    //                         q[x][y] = 0;
    //                         SD_C SD1 = *this;
    //                         SD1.SimpleInit_s();
    //                         if (SD1.FindAnswer())
    //                             q[x][y] = old;
    //                         block[j]++;
    //                     }
    //                 }
    //         }
    //     }
    // }

    //以下程序实现每宫最少留2个，且一共最少留17个//未实现

    for (int i = 0; i < 20; i++) //每宫试挖i次
    {
        for (int j = 0; j < 9; j++) //遍历9个宫
        {
            // cout << j << "宫有" << block[j] << "空" << endl;
            if (block[j] < 7 && blocksum < 60)
            {
                x = v(e) + j % 3 * 3;
                y = v(e) + j / 3 * 3;
                if (q[x][y] != 0)
                {
                    old = q[x][y];
                    q[x][y] = 0;
                    block[j]++;
                    blocksum++;
                    SD_C SD1 = *this;
                    SD1.SimpleInit_s();
                    if (SD1.FindAnswer())
                    {
                        q[x][y] = old;
                        block[j]--;
                        blocksum--;
                    }
                }
            }
        }
    }

    // while(blocksum < 60)
    // {
    //     for (int j = 0; j < 9; j++) //遍历9个宫
    //     {
    //         // cout << j << "宫有" << block[j] << "空" << endl;
    //         if (block[j] < 7 && blocksum < 60)
    //         {
    //             x = v(e) + j % 3 * 3;
    //             y = v(e) + j / 3 * 3;
    //             if (q[x][y] != 0)
    //             {
    //                 old = q[x][y];
    //                 q[x][y] = 0;
    //                 block[j]++;
    //                 blocksum++;
    //                 SD_C SD1 = *this;
    //                 SD1.SimpleInit_s();
    //                 if (SD1.FindAnswer())
    //                 {
    //                     q[x][y] = old;
    //                     block[j]--;
    //                     blocksum--;
    //                 }
    //             }
    //         }
    //     }
    // }

    cout << endl
         << "新的数独：" << endl;
    Print_q(1);
}

//4.递归判断多解
bool SD_C::FindAnswer()
{
    AllFind();

    int result = Check_s(); //检查解题进度:1未完成,0完成,－1出错

    if (result == 0) //完成
    {
        ++t;
        if (t == 2)
        {
            //cout<<"多于1个解"<<endl;
            return true;
        }
        else
            return false;
    }

    if (result == 1) //未完成
    {
        SmallXY();          //找出最少候选数的位置坐标
        short pv = s[x][y]; //pv暂存该位置
        while (pv != 0)
        {
            short testV = HighestOneBit(pv); //提取最高位
            pv -= testV;                     //删除pv的最高位1
            SD_C SD1 = *this;                //生成备份对象SD1
            SD1.s[x][y] = testV;             //在SD1数组上尝试
            bool f = SD1.FindAnswer();       //进入递归
            if (f)
                return true;
        };
    }
    return false;
}
